package algorithms.leaning.class19;

import common.util.MyUtil;

/**
 * 规定1和A对应、2和B对应、3和C对应...26和Z对应
 * 那么一个数字字符串比如"111”就可以转化为:
 * "AAA"、"KA"和"AK"
 * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
 *
 * @author guichang
 * @date 2021/6/18
 */

@SuppressWarnings("all")
public class Code2_动态规划_数字转化字符 {

    public static void main(String[] args) {
        String str = "111111111111111";
        MyUtil.print(transferCount(str));
        MyUtil.print(transferCountDp(str));
    }

    public static int transferCount(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }

    /**
     * index以及往后做决定的种数
     */
    private static int process(char[] cs, int index) {
        // 到最后了，表示有结果
        if (index == cs.length) {
            return 1;
        }
        // 0字符不可转
        if (cs[index] == '0') {
            return 0;
        }
        // 取一位
        int p = process(cs, index + 1);
        // 取两位
        if (index + 1 < cs.length && (cs[index] - '0') * 10 + (cs[index + 1] - '0') < 27) {
            p += process(cs, index + 2);
        }
        return p;
    }

    /**
     * 严格位置依赖版本
     */
    public static int transferCountDp(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] cs = str.toCharArray();
        int N = cs.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        // 从后往前
        for (int index = N - 1; index >= 0; index--) {
            // 0字符不可转
            if (cs[index] == '0') {
                continue;
            }
            // 取一位
            dp[index] = dp[index + 1];
            // 取两位
            if (index + 1 < N && (cs[index] - '0') * 10 + (cs[index + 1] - '0') < 27) {
                dp[index] += dp[index + 2];
            }
        }
        return dp[0];
    }


}